package problems.practice;

import utils.beans.TreeNode;

import java.util.*;

public class Season_2022_fall_contest {
    public int temperatureTrend(int[] tA, int[] tB) {
        int n = tA.length;
        int max = 0;
        int ret = 0;

        for (int i = 1; i < n; ++i) {
            if (tA[i] > tA[i - 1] && tB[i] > tB[i - 1])
                ++max;
            else if (tA[i] < tA[i - 1] && tB[i] < tB[i - 1]) ++max;
            else if (tA[i] == tA[i - 1] && tB[i] == tB[i - 1]) ++max;
            else max = 0;
            ret = Math.max(max, ret);
        }

        return ret;

    }

    public int transportationHub(int[][] path) {
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        HashSet<Integer> ss = new HashSet<>();
        HashSet<Integer> nodeSet = new HashSet<>();

        for (int[] e : path) {
            Set<Integer> set = map.getOrDefault(e[1], null);
            if (set == null) {
                set = new HashSet<>();
                set.add(e[0]);
                map.put(e[1], set);
            } else {
                set.add(e[0]);
            }
            ss.add(e[0]);
            nodeSet.add(e[0]);
            nodeSet.add(e[1]);
        }

        if (ss.size() >= nodeSet.size()) return -1;
        int n = nodeSet.size();

        for (int node : nodeSet) {
            if (!ss.contains(node)) {
                Set<Integer> sss = map.get(node);
                if (sss != null && sss.size() == n - 1) return node;
            }
        }

        return -1;
    }


    public int[][] ballGame(int num, String[] plate) {
//        if (num < 1) return new int[0][];
        int m = plate.length;
        int n = plate[0].length();
        List<int[]> list = new ArrayList<>();

        for (int i = 1; i < m - 1; ++i) {
            if (plate[i].charAt(0) == '.') {
                // 判断当前点能否在 num 步内进洞
                if (bfs(plate, i, 0, 1, num, m, n))
                    list.add(new int[]{i, 0});
                if (bfs(plate, i, n - 1, 3, num, m, n))
                    list.add(new int[]{i, n - 1});
            }
        }

        for (int i = 1; i < n - 1; ++i) {
            if (bfs(plate, 0, i, 2, num, m, n))
                list.add(new int[]{0, i});
            if (bfs(plate, m - 1, i, 0, num, m, n))
                list.add(new int[]{m - 1, i});
        }

        return list.toArray(new int[0][]);
    }

    private boolean bfs(String[] p, int x, int y, int dir, int k, int row, int col) {
        if (k < 1) return false;
        Queue<P> que = new LinkedList<>();
        HashSet<P> visited = new HashSet<>();
        int newX, newY, newDir;
        P po = new P(x, y, dir);
        que.offer(po);
        visited.add(po);

        int[] dx = new int[]{-1, 0, 1, 0};
        int[] dy = new int[]{0, 1, 0, -1};

        while (k > 0 && !que.isEmpty()) {
            po = que.poll();
            newX = po.x + dx[po.dir];
            newY = po.y + dy[po.dir];
            if (checkRange(newX, newY, row, col)) {
                newDir = getDir(p[newX].charAt(newY), po.dir);
                if (newDir < 0) return true;
                po = new P(newX, newY, newDir);
                if (!visited.contains(po)) {
                    que.offer(po);
                    visited.add(po);
                }
            }
            --k;
        }

        return false;
    }

    private int getDir(char c, int dir) {
        // 逆时针
        if (c == 'W') return dir == 0 ? 3 : dir - 1;
        if (c == 'E') return (dir + 1) % 4;
        if (c == '.') return dir;
        return -1;
    }

    private boolean checkRange(int x, int y, int r, int c) {
        return x > -1 && x < r && y > -1 && y < c;
    }

    class P {
        int x;
        int y;
        int dir; // 0: 上，1: 右，2: 下，3: 左

        public P(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            P p = (P) o;
            return x == p.x && y == p.y && dir == p.dir;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y, dir);
        }
    }


    // No.1
    public int minNumBooths(String[] demand) {
        int m = 26;
        int[] map = new int[m];
        int[] tmp = new int[m];
        for (String d : demand) {
            Arrays.fill(tmp, 0);

            for (char c : d.toCharArray()) ++tmp[c - 'a'];

            for (int i = 0; i < m; ++i) {
                map[i] += map[i] >= tmp[i] ? 0 : tmp[i] - map[i];
            }
        }

        return Arrays.stream(map).sum();
    }


    // No.2
    public TreeNode expandBinaryTree(TreeNode root) {
        if (root == null) return root;

        Queue<TreeNode> que = new LinkedList<>();
        TreeNode node, tmp;

        que.offer(root);

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                node = que.poll();

                if (node.left != null) {
                    // 有左孩子
                    tmp = new TreeNode(-1);
                    tmp.left = node.left;
                    node.left = tmp;
                    que.offer(tmp.left);
                }

                if (node.right != null) {
                    // 有右孩子
                    tmp = new TreeNode(-1);
                    tmp.right = node.right;
                    node.right = tmp;
                    que.offer(tmp.right);
                }
            }
        }

        return root;
    }



    // No.3
    static final int MOD = (int) (1e9 + 7);
    public int beautifulBouquet(int[] flowers, int cnt) {
        if (flowers == null || flowers.length < 1 || cnt < 1) return 0;

        HashMap<Integer, Integer> cntMap = new HashMap<>();
        int n = flowers.length;
        int left = 0;
        long ret = 0;
        int k;
        for (int right = 0; right < n; ++right) {
            k = cntMap.getOrDefault(flowers[right], 0);
            if  (k + 1 > cnt) {
                // 当前花不能选
                // 从最左边移除 至与 flowers[right] 相同的一朵花即可
                while (left < right && flowers[left] != flowers[right]) {
                    cntMap.put(flowers[left], cntMap.get(flowers[left]) - 1);
                    ++left;
                }

                // 将相同的花移除
                if (left < right) left++;
            } else {
                cntMap.put(flowers[right], k + 1);
            }
            ret = (ret + (right - left + 1)) % MOD;
        }
        return (int) ret;
    }
}
